package main

import (
	"fmt"
)

func main() {
	// root := &TreeNode{
	// 	Val: 5,
	// 	Left: &TreeNode{
	// 		Val: 4,
	// 		Left: &TreeNode{
	// 			Val: 11,
	// 			Left: &TreeNode{
	// 				Val: 7,
	// 			},
	// 			Right: &TreeNode{
	// 				Val: 2,
	// 			},
	// 		},
	// 	},
	// 	Right: &TreeNode{
	// 		Val: 8,
	// 		Left: &TreeNode{
	// 			Val: 13,
	// 			Right: &TreeNode{
	// 				Val: 4,
	// 				Right: &TreeNode{
	// 					Val: 1,
	// 				},
	// 			},
	// 		},
	// 	},
	// }

	root := &TreeNode{
		Val: -2,
		Right: &TreeNode{
			Val: -3,
		},
	}
	fmt.Println(hasPathSum(root, -5))
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}

	stack := []*struct {
		Node *TreeNode
		Sum  int
	}{
		{
			Node: root,
			Sum:  root.Val,
		},
	}

	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if n.Node.Left == nil && n.Node.Right == nil {
			if n.Sum == targetSum {
				return true
			}
		}

		if n.Node.Left != nil {
			stack = append(stack, &struct {
				Node *TreeNode
				Sum  int
			}{
				Node: n.Node.Left,
				Sum:  n.Sum + n.Node.Left.Val,
			})
		}

		if n.Node.Right != nil {
			stack = append(stack, &struct {
				Node *TreeNode
				Sum  int
			}{
				Node: n.Node.Right,
				Sum:  n.Sum + n.Node.Right.Val,
			})
		}
	}

	return false
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
